package hard;

import easy.删除有序数组中的重复项_26;

import java.util.Arrays;

/**
 * 2009. 使数组连续的最少操作数
 * 创建时间：2024-04-08 14:14
 * 地址：https://leetcode.cn/problems/minimum-number-of-operations-to-make-array-continuous/description/
 */
public class 使数组连续的最少操作数_2009 {
    static class Solution {
        public int minOperations(int[] nums) {
            Arrays.sort(nums);
            // 去除重复项
            int m = 1, n = nums.length;
            for (int i = 1; i < n; i++) {
                if (nums[i] != nums[i - 1]) {
                    nums[m++] = nums[i];
                }
            }

            int ans = 0, left = 0;
            for (int i = 0; i < m; i++) {
                // 这里nums[i] 表示最大值 x， nums[i] - n + 1 表示最小值
                while (nums[left] < nums[i] - n + 1) { // nums[left] 不在窗口内
                    left++;
                }
                // nums[left] 在窗口内时，判断是否比之前的范围大，比较不需要操作的索引位置
                ans = Math.max(ans, i - left + 1);
            }
            return n - ans;
        }

        public static void main(String[] args) {
            Solution s = new Solution();
            int[] nums = {1, 2, 3, 5, 6};
            System.out.println(s.minOperations(nums));
        }
    }
}
